import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网OJ面试必刷题 二叉树
 */
public class Test {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,5,3};
        int[] in = {4,2,5,1,3};
        int[] ret = solve(pre,in);
        System.out.println(Arrays.toString(ret));
    }

    //二叉树的前序遍历（由于最后需要返回一个int型的数组，因此我们采用两种方法来做）
    //方法一
    /*static int[] nums = new int[10];
    int usedSize;

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if(root == null) {
            return new int[0];
        }
        preorder(root);
        return nums;
    }

    public void preorder(TreeNode root) {
        if(root == null) {
            return;
        }
        if(usedSize >= nums.length) {
            nums = Arrays.copyOf(nums,nums.length * 2);
        }
        nums[usedSize++] = root.val;
        preorder(root.left);
        preorder(root.right);
    }*/

    //方法二
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        preorder(root,list);
        int[] nums = new int[list.size()];
        for(int i = 0; i < nums.length; i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    public void preorder(TreeNode root,ArrayList<Integer> list) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }

    //二叉树的中序遍历
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        if(root == null) {
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        inorder(root,list);
        int[] nums = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    public void inorder(TreeNode root,ArrayList<Integer> list) {
        if(root == null) {
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

    //二叉树的后序遍历
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        if(root == null) {
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        postorder(root,list);
        int[] nums = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    public void postorder(TreeNode root,ArrayList<Integer> list) {
        if(root == null) {
            return;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }

    //层序遍历并按行存储
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        fun2(root,list);
        return list;
    }

    /**
     * 层序遍历方法一：使用两个队列
     * 两个队列分别存储一层的节点
     * 上一层的节点一边将子节点放在另一个队列里，一边将自己的节点弹出当前队列
     * 并将val值保存在ArrayList顺序表当中
     * @param root
     * @param list
     */
    public void fun1(TreeNode root,ArrayList<ArrayList<Integer>> list){
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        if(root == null) {
            return;
        }
        Queue<TreeNode> tmp = q1;
        Queue<TreeNode> tmp2 = q2;
        tmp.offer(root);
        while(!tmp.isEmpty() || !tmp2.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            while(!tmp.isEmpty()) {
                TreeNode node = tmp.peek();
                if(node.left != null) {
                    tmp2.offer(node.left);
                }
                if(node.right != null) {
                    tmp2.offer(node.right);
                }
                level.add(node.val);
                tmp.poll();
            }
            list.add(level);
            Queue<TreeNode> t3 = tmp;
            tmp = tmp2;
            tmp2 = t3;
        }
    }

    /**
     * 方法二：在弹出当前一层的节点前，先统计此时队列中元素的个数
     * size == 当前一层元素的个数，然后用for循环进行存储和遍历
     * 不需要多开辟一个队列，效率提高
     * @param root
     * @param list
     */
    public void fun2(TreeNode root,ArrayList<ArrayList<Integer>> list){
        Queue<TreeNode> q = new LinkedList<>();
        if(root == null) {
            return;
        }
        q.offer(root);
        while(!q.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            //关键所在
            int size = q.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = q.peek();
                if(node.left != null) {
                    q.offer(node.left);
                }
                if(node.right != null) {
                    q.offer(node.right);
                }
                level.add(node.val);
                q.poll();
            }
            list.add(level);
        }
    }

    //按之字型顺序打印二叉树
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot == null) {
            return list;
        }
        fun4(pRoot,list);
        return list;
    }

    /**
     * 方法一：用一个队列和一个栈实现，如果需要逆序的
     * 先放在栈里面，再逐个add到ArrayList表里
     * @param root
     * @param list
     */
    public void fun3(TreeNode root,ArrayList<ArrayList<Integer>> list) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;
        while(!q.isEmpty()) {
            ArrayList<Integer> l = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            int size = q.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = q.peek();
                if(node.left != null) {
                    q.offer(node.left);
                }
                if(node.right != null) {
                    q.offer(node.right);
                }
                TreeNode tmp = q.poll();
                if(level % 2 == 0) {
                    l.add(node.val);
                }else {
                    stack.push(tmp);
                }
            }
            while(!stack.empty()) {
                l.add(stack.pop().val);
            }
            level++;
            list.add(l);
        }
    }

    /**
     * 方法二：直接利用两个栈，交替放，不用在逆序的时候遍历两遍，减少时间复杂度
     * @param root
     * @param list
     */
    public void fun4(TreeNode root,ArrayList<ArrayList<Integer>> list) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        int level = 0;
        while(!stack1.empty()) {
            ArrayList<Integer> l = new ArrayList<>();
            int size = stack1.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = stack1.peek();
                if(level % 2 == 0) {
                    if(node.left != null) {
                        stack2.push(node.left);
                    }
                    if(node.right != null) {
                        stack2.push(node.right);
                    }
                }else {
                    if(node.right != null) {
                        stack2.push(node.right);
                    }
                    if(node.left != null) {
                        stack2.push(node.left);
                    }
                }
                stack1.pop();
                l.add(node.val);
            }
            level++;
            list.add(l);
            Stack<TreeNode> tmp = stack1;
            stack1 = stack2;
            stack2 = tmp;
        }
    }

    //求二叉树的最大深度
    public int maxDepth (TreeNode root) {
        // write code here
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) ,maxDepth(root.right)) + 1;
    }

    //二叉树中和为某一值的路径（一）
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null && sum == root.val) {
            return true;
        }
        boolean left = hasPathSum(root.left, sum - root.val);
        if(left) {
            return true;
        }
        boolean right = hasPathSum(root.right, sum - root.val);
        return right;
    }

    //二叉搜索树与双向链表

    /**
     * 方法一：看似后序遍历，实则中序遍历递归
     * 因为我们只是在后序遍历完对根节点的right和后面节点的left再进行一点修改
     * 归根结底，仍是按照中序遍历将一个个节点纳入到新的双向链表中
     * 得到子树更改后的头尾节点，然后用root将两个链表链接
     * 时间复杂度为：O(N)
     * 空间复杂度为：O(N)，主要是因为递归，并没有创建新的节点
     * @param pRootOfTree
     * @return
     */
    /*public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        TreeNode[] nodes = fun(pRootOfTree);
        return nodes[0];
    }

    public TreeNode[] fun(TreeNode root) {
        TreeNode start = root;
        TreeNode end = root;
        if(root.left == null && root.right == null) {
            TreeNode[] nodes = {root,root};
            return nodes;
        }
        if(root.left != null) {
            TreeNode[] nodesLeft = fun(root.left);
            nodesLeft[1].right = root;
            root.left = nodesLeft[1];
            start = nodesLeft[0];
        }
        if(root.right != null) {
            TreeNode[] nodesRight = fun(root.right);
            nodesRight[0].left = root;
            root.right = nodesRight[0];
            end = nodesRight[1];
        }
        TreeNode[] nodes = {start,end};
        return nodes;
    }*/

    /**
     * 方法一改善：节点前的链表的最后一个节点设置为成员变量
     * 递归方法返回递归之后链表的头节点
     * 时间复杂度为：O(N)
     * 空间复杂度为：O(N)
     * @param pRootOfTree
     * @return
     */
    TreeNode tail = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        return fun5(pRootOfTree);
    }

    public TreeNode fun5(TreeNode root) {
        TreeNode head = null;
        if(root == null) {
            return null;
        }
        //当root是叶子节点的时候，那么对于这个小递归而言，叶子节点即是头节点，也是尾节点
        if(root.left == null && root.right == null) {
            tail = root;
            return root;
        }
        //对于根节点而言，调用左子树返回结果就是新的左边的链表的头节点，需要保存
        //而前面链表的尾节点已经保存在tail值（如何保证没问题？）
        //解释：看下面root.left的代码，当root.left不为null时
        //先遍历左子树，由分治法
        // 1.当遇到叶子节点的时候，tail更新为叶子节点
        //对于根节点而言，此时tail的节点就是根节点链表的前一个节点，并把tail更新为根节点
        // 2.假设左子树不止一个节点，且左子树的右子树存在了节点
        // 由于我们采用的是中序遍历，当左子树递归到左子树的右子树时
        // 遇到最右边的叶子节点时，上面判断是否为叶子节点的代码就已经将tail更改为左子树的右下节点
        // 如果左子树的右下是一个只有左子树的根节点，那么下方的代码也会将tail更新成右下的根节点
        if(root.left != null) {
            head = fun5(root.left);
            tail.right = root;
            root.left = tail;
            tail = root;
        }
        //如果只有右子树，这里对head不进行操作的话
        //那么head的值就是null，而实际上理应head == root;
        //因此加个判断条件
        if(head == null) {
            head = root;
        }
        //这里是对根节点和右子树遍历返回的头节点进行操作
        if(root.right != null) {
            TreeNode start = fun5(root.right);
            start.left = root;
            root.right = start;
        }
        //最后返回新链表的头节点
        return head;
    }

    //递归判断是否是对称二叉树
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        return fun6(pRoot.left,pRoot.right);
    }

    //递归判断，利用两个形参分别存放左右子树的节点
    public boolean fun6(TreeNode left,TreeNode right) {
        //叶子节点，返回true
        if(left == null && right == null) {
            return true;
        }
        //当两个节点只有一个为null 或者 两者值不相等时，返回false
        if(left == null || right == null || left.val != right.val) {
            return false;
        }
        //此时返回的前提就是left和right都不为null 且二者val值相等
        //我们只需要判断它们的左右子树是否也是对称，当都是对称的时候，才能返回true
        return fun6(left.left,right.right) && fun6(left.right,right.left);
    }

    //迭代判断二叉树是否对称
    boolean isSymmetrical2(TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        //迭代，利用两个队列，将根节点的左右子树看成两棵独立的子树
        Queue<TreeNode> qu1 = new LinkedList<>();
        Queue<TreeNode> qu2 = new LinkedList<>();
        qu1.offer(pRoot.left);
        qu2.offer(pRoot.right);
        while(!qu1.isEmpty() && !qu2.isEmpty()) {
            TreeNode left = qu1.poll();
            TreeNode right = qu2.poll();
            if(left == null && right == null) {
                continue;
            }
            if(left == null || right == null || left.val != right.val) {
                return false;
            }
            qu1.offer(left.left);
            qu1.offer(left.right);
            qu2.offer(right.right);
            qu2.offer(right.left);
        }
        return true;
    }

    /**
     * 合并二叉树
     * 递归实现
     * 空间复杂度：O(N)，只有递归栈的空间
     * 时间复杂度：O(N)，最坏情况下需要遍历每个节点
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1 == null && t2 == null) {
            return null;
        }
        if(t1 == null) {
            return t2;
        }
        if(t2 == null) {
            return t1;
        }
        //分别进行判断时候还需要向左子树遍历或向右子树遍历
        boolean flg1 = false;
        boolean flg2 = false;
        t1.val = t1.val + t2.val;
        //如果存在一个节点的左子树为空，另一个节点的左子树不为空
        //将不为空的左子树放在t1的左子树下，并将flg1置为true
        //当flg1为true时，表示不需要再遍历两个根节点的左子树了
        if(t1.left == null && t2.left != null) {
            flg1 = true;
            t1.left = t2.left;
        } else if(t1.left != null && t2.left == null) {
            flg1 = true;
        }
        //右子树同理
        if(t1.right == null && t2.right != null) {
            flg2 = true;
            t1.right = t2.right;
        } else if(t1.right != null && t2.right == null) {
            flg2 = true;
        }
        if(!flg1) {
            mergeTrees(t1.left,t2.left);
        }
        if(!flg2) {
            mergeTrees(t1.right,t2.right);
        }
        return t1;
    }

    /**
     * 二叉树的镜像，即以根节点为对称轴进行反转
     * @param pRoot
     * @return
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return pRoot;
        }
        //从上到下依次交换
        swap(pRoot);
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }

    public void swap(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }

    /**
     * 判断是不是二叉搜索树？
     * 二叉搜索树的中序遍历一定是升序的
     * 设置一个 prevVal 来记录中序遍历过程中前一个位置的节点 val 值
     * @param root
     * @return
     */
    static Integer prevVal = null;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null || (root.left == null && root.right == null)) {
            return true;
        }
        return fun7(root);
    }

    //中序遍历
    public boolean fun7(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean flg;
        flg = fun7(root.left);
        if(!flg) {
            return false;
        }
        if(prevVal == null) {
            prevVal = root.val;
        }else {
            if(prevVal > root.val) {
                return false;
            }else {
                prevVal = root.val;
            }
        }
        flg = fun7(root.right);
        if(!flg) {
            return false;
        }
        return true;
    }

    //判断是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        //利用层序遍历，孩子节点为null也存储
        //当遇到null并且后面都是null的时候就是完全二叉树
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node == null) {
                break;
            }else {
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断是不是平衡二叉树方法一：从下往上比较，只遍历一次，时间复杂度O(N)
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        //类似找二叉树的深度，需要进行比较
        if(root == null) {
            return true;
        }
        int ret = fun8(root);
        if(ret < 0) {
            return false;
        }else {
            return true;
        }
    }

    //从下往上，从左往右判断，遍历次数少
    //返回值为int才能得到深度和子树的差值，否则无法比较
    public int fun8(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        //比较根节点两个子树的深度
        int left = fun8(root.left);
        if(left < 0) {
            return -1;
        }
        int right = fun8(root.right);
        if(right < 0) {
            return -1;
        }
        //得到左右子树深度的差值
        int ans = Math.abs(left - right);
        //返回-1，表示下面已经不平衡了，因此上面两个返回值也需要判断
        if(ans > 1) {
            return -1;
        }
        //返回根节点的最大深度
        return Math.max(left,right) + 1;
    }

    /**
     * 方法二：从上往下比较，时间复杂度高，达到了O(N ^ 2)
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution2(TreeNode root) {
        //类似找二叉树的深度，需要进行比较
        if(root == null) {
            return true;
        }
        if(Math.abs(fun9(root.left) -
                fun9(root.right)) > 1) {
            return false;
        }
        return IsBalanced_Solution2(root.left) &&
                IsBalanced_Solution2(root.right);
    }

    //返回值为int才能得到深度，否则无法比较
    public int fun9(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(fun9(root.left),fun9(root.right)) + 1;
    }

    /**
     * 二叉搜索树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        //类似寻找两个链表的第一个公共节点
        //1.先利用栈得到两个节点的路径并统计路径节点数
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        findNode2(root,p,s1);
        findNode2(root,q,s2);
        int size1 = s1.size();
        int size2 = s2.size();
        //2.将节点数多的栈出栈操作，直到两个栈的节点数量相同
        if(size1 > size2) {
            while(size1 > size2) {
                s1.pop();
                size1--;
            }
        }else {
            while(size1 < size2) {
                s2.pop();
                size2--;
            }
        }
        //3.两个栈一起出栈，比较
        while(!s1.empty() && !s2.empty()) {
            if(s1.peek() == s2.peek()) {
                return s1.peek().val;
            }
            s1.pop();
            s2.pop();
        }
        return -1;
    }

    //方法一：先序遍历查找
    public boolean findNode(TreeNode root,int num,Stack<TreeNode> s) {
        if(root == null) {
            return false;
        }
        s.push(root);
        if(root.val == num) {
            return true;
        }
        boolean flg = false;
        flg = findNode(root.left,num,s);
        if(flg) {
            return true;
        }
        flg = findNode(root.right,num,s);
        if(flg) {
            return true;
        }
        s.pop();
        return false;
    }

    //方法二：由于二叉树是搜索树，因此我们可以通过比较root.val和num的值来决定
    //找到后直接返回或者往左遍历或往右遍历
    public void findNode2(TreeNode root,int num,Stack<TreeNode> s) {
        if(root == null) {
            return;
        }
        s.push(root);
        if(root.val == num) {
            return;
        }
        if(num < root.val) {
            findNode2(root.left,num,s);
        }else {
            findNode2(root.right,num,s);
        }
        return;
    }

    //在二叉树中找到两个节点的最近公共祖先

    /**
     * 解法：先序遍历，只用遍历一遍
     * 情况：1.当两个节点中某一个节点是root时，那么公共节点就是root，即一个节点是另一个节点的根节点
     * 2.如果在root值的两边，那么 left 和 right 最后都会返回到root且 >= 0，公共节点还是root
     * 3.如果在root的左或者右子树的下面，那么到root的时候只有 left 或 right >= 0，
     *  那么我们直接返回当前这个值即可
     * @param root
     * @param o1
     * @param o2
     * @return
     */
    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) {
            return -1;
        }
        if(root.val == o1 || root.val == o2) {
            return root.val;
        }
        int left = lowestCommonAncestor1(root.left,o1,o2);
        int right = lowestCommonAncestor1(root.right,o1,o2);
        if(left >= 0 && right >= 0) {
            return root.val;
        }else if(left >= 0) {
            return left;
        }else {
            return right;
        }
    }

    //用在重构二叉树中
    int i = -1;
    //先序遍历实现

    /**
     * 序列化二叉树和重构（反序列）二叉树
     * 前序遍历非常简单，层序遍历需要创建虚拟节点，非常麻烦
     * @param root
     * @return
     */
    String Serialize(TreeNode root) {
        if(root == null) {
            return null;
        }
        StringBuilder s = new StringBuilder();
        fun10(root,s);
        return s.toString();
    }
    TreeNode Deserialize(String str) {
        if(str == null || str.equals("")) {
            return null;
        }
        String[] s = str.split(",");
        return funBack(s);
    }

    private void fun10(TreeNode root, StringBuilder s) {
        if(root == null) {
            s.append("#,");
            return;
        }
        s.append(root.val);
        s.append(",");
        fun10(root.left,s);
        fun10(root.right,s);
    }

    private TreeNode funBack(String[] s) {
        i++;
        if(i == s.length || s[i].equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s[i]));
        root.left = funBack(s);
        root.right = funBack(s);
        return root;
    }

    //记录pre的位置
    static int index = -1;
    /**
     * 利用先序遍历数组和中序遍历数组构建二叉树
     * @param pre
     * @param vin
     * @return
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length == 0 || vin.length == 0) {
            return null;
        }
        return creatTree(pre,vin,0,vin.length - 1);
    }

    //left和right作为利用pre得到根节点之后的左子树和右子树
    private static TreeNode creatTree(int[] pre,int[] vin,int left,int right) {
        //如果left > right，表示该节点为null,index不应该+1
        //因为先序遍历并没有保存null，会导致index多走一步
        //因此index走的前提是保证子树 != null
        if(left > right || ++index >= pre.length) {
            return null;
        }
        TreeNode root = new TreeNode(pre[index]);
        int i = left;
        for(; i < right; i++) {
            if(pre[index] == vin[i]) {
                break;
            }
        }
        root.left = creatTree(pre,vin,left,i - 1);
        root.right = creatTree(pre,vin,i + 1,right);
        return root;
    }

    /*int index = -1;*/

    /**
     * 输出二叉树的右视图
     * 由于题目要求先按照先序遍历和中序遍历创建二叉树，因此可以直接调用上一道题的代码
     * 然后利用类似计算二叉树深度的方法来得到右视图的数组
     * @param xianxu
     * @param zhongxu
     * @return
     */
    public static int[] solve(int[] xianxu, int[] zhongxu) {
        // write code here
        index = -1;
        if(xianxu.length == 0 || zhongxu.length == 0) {
            return new int[0];
        }
        TreeNode root = creatTree(xianxu,zhongxu,0,zhongxu.length - 1);
        ArrayList<Integer> arr = fun(root);
        int[] nums = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++) {
            nums[i] = arr.get(i);
        }
        return nums;
    }

    private static ArrayList<Integer> fun(TreeNode root) {
        if(root == null) {
            return null;
        }
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(root.val);
        ArrayList<Integer> arrLeft = fun(root.left);
        ArrayList<Integer> arrRight = fun(root.right);
        int i = 0;
        //注意：arrLeft和arrRight都可能为null，因此必须先进行判断
        //否则调用size()方法会报空指针异常
        if(arrRight != null) {
            for(; i < arrRight.size(); i++) {
                arr.add(arrRight.get(i));
            }
        }
        if(arrLeft != null) {
            for (; i < arrLeft.size(); i++) {
                arr.add(arrLeft.get(i));
            }
        }
        return arr;
    }
}
